// FRAOZO - Project 6b

#include <iostream>
#include <limits.h>
#include "d_except.h"
#include <list>
#include <fstream>
#include "d_matrix.h"
#include "graph.h"
#include <queue>
#include <vector>

//Used for getNeighbors - if passed to getNeighbors as third
// parameter, it will return all neighbors (regardless of visit)
#define ALLNEIGHBORS false

#define MAXWEIGHT 99999

using namespace std;

struct nodePair
//Used for storing a node pair, so the resulting
//  edge can be easily made in the spanning forest
{
  int node1;
  int node2;
  int weight;
};


vector<int> getNeighbors(const graph &g, int nodeId, 
                         bool onlyUnVisited = true)
//return a vector of all neighbors of node nodeId
// if countVisited is true, do not include visited neighbors
{
  vector<int> neighbors;
   
  //foreach node in the graph
  for (int candidate=0; candidate<g.numNodes(); candidate++)
    {
      if (candidate == nodeId)
	continue;
      
      if (onlyUnVisited)
	{
	  if (g.isEdge(nodeId, candidate) && !g.isVisited(candidate))
	    neighbors.push_back(candidate);
	}
      else 
	{
	  if (g.isEdge(nodeId, candidate))
	    neighbors.push_back(candidate);
	}
    }

  return neighbors;
} // end getNeighbors

void traverseGraph(graph &g, int startNode)
//From the startnode, visit every neighbor until there are
// no unvisited neighbors
{
  g.visit(startNode);
   
  vector<int> neighbors = getNeighbors(g, startNode);

  //foreach unvisited neighbor
  for (int idx=0; idx<neighbors.size(); idx++)
    {
      int neighbor = neighbors[idx];
      traverseGraph(g, neighbor);
    }
   
} // end traverseGraph

bool hasCycle(graph &g, int currentNode, int prevNode = 0)
//Called recursively.  If a neighbor of currentNode is already visited
//  and is not the prevNode, g contains a cycle
{
  g.visit(currentNode);
   
  //get ALL neighbors - even if some are visited
  vector<int> neighbors = getNeighbors(g, currentNode, ALLNEIGHBORS);

  for (int idx=0; idx<neighbors.size(); idx++)
    {
      int neighbor = neighbors[idx];

      //Skip the node that we came from
      if (neighbor == prevNode)
	continue;

      //base case - one of the neighbors is visited, 
      // and is not the prevNode
      if (g.isVisited(neighbor))
	return true;

      //Recurse.  If true, unwind.  Note that the currentNode 
      //   will become the prevNode, and the neighbor will
      //   become the currentNode
      if (hasCycle(g, neighbor, currentNode))
	return true;
    }

  return false;
} // end hasCycle

bool isCyclic(graph &g)
// Returns true if the graph g contains a cycle.  Otherwise, returns false.
{
  //foreach unvisited node,
  for (int node=0; node<g.numNodes(); node++)
    if (!g.isVisited(node))
      if (hasCycle(g, node))
	{
	  g.clearVisit();
	  return true;
	}

  g.clearVisit();
  return false;
} // end isCyclic

nodePair findCheapestPair(graph &g)
//Find two nodes such that node1 is marked, node 2 is unmarked, 
//  and (node1, node2) has minimum edge weight
// If cheapestPair.weight == MAXWEIGHT, there are no valid edges left
{
  nodePair cheapestPair;
  int smallestWeight = MAXWEIGHT;

  //foreach node in the graph
  for (int startNode=0; startNode<g.numNodes(); startNode++)
    {
      if (g.isVisited(startNode))
	{
	  vector<int> neighbors = getNeighbors(g, startNode);

	  //foreach unvisited neighbor of startNode
	  for (int idx = 0; idx < neighbors.size(); idx++)
	    {
	      int neighbor = neighbors[idx];
	      int weight = g.getEdgeWeight(startNode, neighbor);
	      //If the edge weight is the smallest thus far...
	      if (weight < smallestWeight)
		{
		  smallestWeight = weight;
		  cheapestPair.node1 = startNode;
		  cheapestPair.node2 = neighbor;
		}
	    }

	}
    }

  cheapestPair.weight = smallestWeight;
  return cheapestPair;

} //end findCheapestPair

void prim (graph &g, graph &sf, int startNode)
//Use Prim's Algorithm to build a graph sf from graph g
{
  g.clearVisit();

  g.visit(startNode);
  sf.visit(startNode);

  //do numNodes - 1 iterations (worst case)
  for (int iter=0; iter<g.numNodes() - 1; iter++)
    {
      nodePair cheapestPair = findCheapestPair(g);

      //Check if cheapestPair found a real edge
      if (cheapestPair.weight == MAXWEIGHT)
	//Our current graph portion is all connected - end prim
	return;

      int node = cheapestPair.node1;
      int neighbor = cheapestPair.node2;
      
      //create a bidi edge
      int weight1 = g.getEdgeWeight(node, neighbor);
      int weight2 = g.getEdgeWeight(neighbor, node);
      sf.addEdge(node, neighbor, weight1);
      sf.addEdge(neighbor, node, weight2);

      g.visit(neighbor);
      sf.visit(neighbor);
    }
} // end prim


void findSpanningForest(graph &g, graph &sf)
// Create a graph sf that contains a spanning forest on the graph g.  
{
  //foreach unvisited node, do a call to prim from that node
  for (int node=0; node<g.numNodes(); node++)
    if (!sf.isVisited(node))
      prim(g, sf, node);

  g.clearVisit();
  sf.clearVisit();

} // end findSpanningForest

bool isConnected(graph &g)
// Returns true if the graph g is connected.  Otherwise returns false.
{
  int startNode = 0;
  traverseGraph(g, startNode);
  bool returnVal = g.allNodesVisited();
  g.clearVisit();
  return returnVal;
} // end isConnected

int main(int argc, char* argv[])
{
  char x;
  ifstream fin;
  string fileName;
   
  // Read the name of the graph from the keyboard or
  // hard code it here for testing.
   
  fileName = (argc == 2) ? argv[1] : "graph1.txt";

  fin.open(fileName.c_str());
  if (!fin)
    {
      cerr << "Cannot open " << fileName << endl;
      return 1;
    }

  try

    {
      cout << "Reading graph" << endl;
      graph g(fin);
      cout << g;

      connected = isConnected(g);
      cyclic = isCyclic(g);

      if ( isConnected(g) )
	cout << "Graph is connected" << endl;
      else
	cout << "Graph is not connected" << endl;

      if ( isCyclic(g) )
	cout << "Graph contains a cycle" << endl;
      else
	cout << "Graph does not contain a cycle" << endl;

      cout << endl;
     
      cout << "Finding spanning forest" << endl;

      // Initialize an empty graph to contain the spanning forest
      graph sf(g.numNodes());
      findSpanningForest(g,sf);

      cout << sf;

      cout << "Spanning forest weight: " << sf.getTotalEdgeWeight()/2 << endl;

      connected = isConnected(sf);
      cyclic = isCyclic(sf);

      if (connected)
	cout << "Graph is connected" << endl;
      else
	cout << "Graph is not connected" << endl;

      if (cyclic)
	cout << "Graph contains a cycle" << endl;
      else
	cout << "Graph does not contain a cycle" << endl;

      cout << endl;

    }    
  catch (indexRangeError &ex) 
    { 
      cout << ex.what() << endl; return 1;
    }
  catch (rangeError &ex)
    {
      cout << ex.what() << endl; return 1;
    }
}

